﻿using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

namespace ns
{

    public class Note1 : MonoBehaviour
    {
        //快速排序
        //1.先写快速排序的框架
        public void QuickSort(int[] arr)
        {
            QuickSort(arr,0,arr.Length-1);
        }

        private void QuickSort(int[] arr, int left, int right)
        {
            int middle = Partition(arr,left,right); 
            QuickSort(arr,left,middle-1);
            QuickSort(arr, middle, right);
        }

        private int Partition(int[] arr, int left, int right)
        {
            int pivot = arr[left];
            int start = left;
            int end = right;
            while (start<end)
            {
                while (start < end && arr[start] <= pivot) start++; //找到左边第一个大于基数的位置
                while (start < end && arr[end] <= pivot) end--; //找到右边第一个小于基数的位置
                if (start<end)
                {
                    Swap(arr, start, end);
                    start++;
                    end--;
                }
            }
            //判断是否左右指针相等
            if (start == end && arr[end] <= pivot) end--;
            Swap(arr,start,end);
            return end;
        }

        private void Swap(int[] arr, int start, int end)
        {
            arr[end] = arr[end] + arr[start];
            arr[start] = arr[end] - arr[start];
            arr[end] = arr[end] - arr[start];

        }
    }
}
